#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int n,m,s,a;
string card;
map<string,int> ma;
struct Stu{
    string id;
    int grade;
};

int cmp(Stu &s1,Stu &s2){
    if(s1.grade==s2.grade)    return s1.id<s2.id;
    return s1.grade>s2.grade;
}

signed main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>card>>s;
        ma[card] = s;
    }
    for(int i=0;i<m;i++){
        cin>>a;
        if(a==1){
            char c;
            cin>>c;
            cout<<"Case "<<i+1<<": "<<a<<" "<<c<<"\n";
            Stu stu[10000];
            int cnt = 0;
            for(auto it:ma){
                if(it.first[0]==c){
                    stu[cnt].id = it.first;
                    stu[cnt++].grade = it.second;
                }
            }
            sort(stu,stu+cnt,cmp);
            for(int i=0;i<cnt;i++){
                cout<<stu[i].id<<" "<<stu[i].grade<<"\n";
            }
            if(cnt==0)    cout<<"NA\n";
        }
        if(a==2){
            string site;
            cin>>site;
            cout<<"Case "<<i+1<<": "<<a<<" "<<site<<"\n";
            int sum = 0,sumgrade = 0;
            for(auto it:ma){
                if(it.first.substr(1,3)==site){
                    sum++;
                    sumgrade += it.second;
                }
            }
            if(sum==0)    cout<<"NA\n";
            else    cout<<sum<<" "<<sumgrade<<"\n";
        }
        if(a==3){
            string test;
            cin>>test;
            cout<<"Case "<<i+1<<": "<<a<<" "<<test<<"\n";
            map<string,int> t;
            Stu stu[10000];
            int cnt = 0;
            for(auto it:ma){
                if(it.first.substr(4,6)==test){
                    t[it.first.substr(1,3)]++;
                }
            }
            for(auto it:t){
                stu[cnt].id = it.first;
                stu[cnt++].grade = it.second;
            }
            sort(stu,stu+cnt,cmp);
            for(int i=0;i<cnt;i++){
                cout<<stu[i].id<<" "<<stu[i].grade<<"\n";
            }
            if(cnt==0)    cout<<"NA\n";
        }
    }
    return 0;
}
